This is a randomized placebo-controlled study to determine the efficacy of Azithromycin for primary prevention of Mycobacterium Avium Complex (MAC) and other infections in subjects who have acheived an increase in CD4 cells (from < 50 to >100 cells/mm3) on antiretroviral therapy. Subjects may not have had a prior diagnosis of MAC and will receive 1200 mg of Azithromycin once a week. The primary endpoint is to compare the time to development of MAC. There are numerous secondary objectives and several substudies evaluating azithromycin's effect on other bacterial infections common in the HIV+ patient.